import java.util.*;


public class Solution14 {
    public static void main(String[] args) {
        Solution14 solution = new Solution14();
        List<String> wordList = new ArrayList<>();
        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");
        List<List<String>> ladders = solution.findLadders("hit", "cog", wordList);

//        int i = solution.ladderLength("hit", "cog", wordList);
//        System.out.println(i);
    }
    private List<List<String>> result = new ArrayList<>();
    private int min;
    Set<String> set = new HashSet<>();
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        //预处理wordList
        Map<String,List<String>> wordMap = new HashMap<>();
        min = wordList.size();
        for(String word:wordList){
            for(int i=0;i<word.length();i++){
                String key = word.substring(0,i)+"*"+word.substring(i+1);
                List<String> values = wordMap.getOrDefault(key,new ArrayList<String>());
                values.add(word);
                wordMap.put(key,values);
            }
        }
        List<String> list = new ArrayList<>();
        list.add(beginWord);
        _fidLadders(beginWord, endWord, wordMap, list);
        List<List<String>> sortresult = new ArrayList<>();
        for(List<String> r:result){
            if(r.size()==min){
                sortresult.add(r);
            }
        }
        return sortresult;
    }

    private List<List<String>> _fidLadders(String beginWord, String endWord, Map<String, List<String>> wordMap, List<String> list) {
        if(beginWord.equals(endWord)){
            min = Math.min(min,list.size());
            result.add(new ArrayList<>(list));
            return result;
        }
        for(int i =0;i<beginWord.length();++i){
            String key = beginWord.substring(0,i)+"*"+beginWord.substring(i+1);
            List<String> wordList = wordMap.get(key);
            if(null == wordList)continue;
            for(String word:wordList){
                if(!set.contains(word)) {
                    set.add(word);
                    list.add(word);
                    _fidLadders(word, endWord, wordMap, list);
                    list.remove(word);
                    set.remove(word);
                }
            }
        }
        return result;
    }
}
